// 思路：分治思想，递归分割将序列一分为二，然后归并的过程中将两个有序序列合并成一个有序序列

function mergeSort(arr) {
    if (arr.length <= 1) {
        return arr
    }
    let mid = Math.floor(arr.length / 2)
    let leftArr = mergeSort(arr.slice(0, mid))
    let rightArr = mergeSort(arr.slice(mid))
    return merge(leftArr, rightArr)
}

function merge(leftArr, rightArr) {
    let result = []
    let leftIndex = 0
    let rightIndex = 0
    while (leftIndex < leftArr.length && rightIndex < rightArr.length) {
        if (leftArr[leftIndex] < rightArr[rightIndex]) {
            result.push(leftArr[leftIndex])
            leftIndex++
        } else {
            result.push(rightArr[rightIndex])
            rightIndex++
        }
    }
    if (leftIndex < leftArr.length) {
        result = result.concat(leftArr.slice(leftIndex))
    }
    if (rightIndex < rightArr.length) {
        result = result.concat(rightArr.slice(rightIndex))
    }
    return result
}

// 时间复杂度为Onlogn
// 空间复杂度为On
// 稳定排序

let arr = [6, 2, 1, 3, 7, 5, 4, 8]
console.log(mergeSort(arr))